package test;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 东莞呵呵
 * Date:2022-07-27
 * Time:16:48
 */
public class HeapSort implements ISort{
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public void createTree(int[] array){
        for (int i = (array.length-1-1)/2; i >= 0; i--) {
            siftDown(array,0,array.length);
        }
    }
    public void siftDown(int[] array,int parent,int len){
        int child=2*parent+1;
        while(child<len){
            if(child+1<len&&array[child]<array[child+1]){
                child++;
            }
            if(array[parent]<array[child]){
                swap(array,parent,child);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }
    public void sort(int[] array){
        System.out.println("堆排序：");
        createTree(array);
        int end=array.length -1;
        while(end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }

    }
}
